//*********************************************************************
//
// Hydra Memory System Model for the MIPSY simulator under SimOS
//
// the Hydra Group, February-July 1996
//
// C++ file containing the simulator's objects.
//
// This particular header contains all information pertinent to the
// operation of a latency histogram object.
//
//*********************************************************************

#include "util/Histogram.h"

//*********************************************************************
// The Histogram Object
//
// This object maintains a histogram of values that are fed into it,
// and can print it out whenever it is desired.
//*********************************************************************

NEW_DELETE_OPERATORS_CPP(Histogram,100);

// The initializer/destructor pair sets up the histogram.
// The user should choose a size of the last true bucket
// of the histogram -- the system will automatically add
// a "tail" bucket to catch extreme cases.
Histogram::Histogram (int _size, const char* _name) :
    name(_name),
    size(_size)
{
    // Allocate array space
    items = (int*)CALLOC(size+3, sizeof(int));

    // And clear everything out
    for (int i=0; i < (size+2); i++) 
        items[i] = 0;
    time = 0;
    totalA = 0;
    totalB = 0;
    count = 0;
    minimum = 0;
    maximum = 0;
}

Histogram::~Histogram () {
    FREE(items);
}

// The private PrintBar function is just to print a histogram bar
void Histogram::printBar (int size, double scale, FILE *output, const char* prefix) {
    // Calculate the length of the bar
    bool endFlag = FALSE;
    int end = (int)((1.0*size)*scale);
    if (end > peakBarHeight) {
        end = peakBarHeight;
        endFlag = TRUE;
    }

    // Make sure bars with few elements don't entirely disappear
    if ((end == 0) && (size > 0)) 
        end = 1;

    // Print the stuff out
    for (int i=0; i < end; i++) {
        fprintf(output, "*");
    }
    if (endFlag) 
        fprintf(output,"-->");
    fprintf(output,"\n");
}

// PrintStats prints out the histogram
void Histogram::printStats(FILE *output, const char* prefix) {
    // Pre-search for beginning, end, and averages
    //
    // Mode
    int peak = items[size + 2];
    int second = items[size + 2];
    int mode = size + 2;
    if (items[size + 1] > peak) {
        peak = items[size+1];
        mode = size + 1;
    }
    //
    // Median
    int curCount = items[size + 2];
    int ten = (int) ((double)count * 0.10);
    int twentyfive  = (int) ((double)count * 0.25);
    int halfway = (int) ((double)count * 0.50);
    int seventyfive = (int) ((double)count * 0.75);
    int ninety = (int) ((double)count * 0.90);
    int tenthPercent = -1;
    int twentyfivePercent = -1;
    int median = -1;
    int seventyfivePercent = -1;
    int ninetyPercent = -1;

    //
    // Beginning & end
    int beginning = -1;
    int end = 0;
    for (int i=0; i <= size; i++) {
        // Adjust mode
        if (items[i] > peak) {
            peak = items[i];
            mode = i;
        }
        else if (items[i] > second)
            second = items[i];

        // Adjust median & percentiles
        curCount += items[i];
        if ((curCount > ten) && (tenthPercent == -1)) 
            tenthPercent = i;
        if ((curCount > twentyfive) && (twentyfivePercent == -1))
            twentyfivePercent = i;
        if ((curCount > halfway) && (median == -1)) 
            median = i;
        if ((curCount > seventyfive) && (seventyfivePercent == -1))
            seventyfivePercent = i;
        if ((curCount > ninety) && (ninetyPercent == -1)) 
            ninetyPercent = i;

        // Adjust beginning and end
        if (items[i] > 0) {
            if (beginning == -1) beginning = i;
            end = i;
        }
    }

    // Determine stepsize for "long" histograms w/ combined bars
    int step;
    if (end - beginning + 1 <= longestHistogramSize)
        step = 1;
    else {
        step = ((end-beginning+1) / longestHistogramSize) + 1;

        // And recalculate peak/second values based upon this
        for (int i=beginning; i <= end; i+=step) {
            // Accumulate bars together for "long" histograms
            int itemPrint = 0;
            for (int j=i; j < i+step; j++)
                itemPrint += items[j];

            // Adjust peak/second
            if (itemPrint > peak)
                peak = itemPrint;
            else if (itemPrint > second)
                second = itemPrint;
        }
    }

    // Header stuff
    fprintf(output, "%s    Latency/Size Histogram for %s:\n",prefix,name);

    // Draw the histogram if there's anything to put in it
    if (count > 0) {
        // Header of summary information
        fprintf(output, "%s      Averages: mean = %7.2f, median = %d, mode = %d\n",
                prefix, (1.0e9*totalB + 1.0*totalA)/(1.0*count), median, mode);
        fprintf(output,
                "%s      Percentiles: 10%% = %d, 25%% = %d, 50%% = %d, 75%% = %d, 90%% = %d\n",
                prefix, tenthPercent, twentyfivePercent, median, seventyfivePercent, ninetyPercent);
        fprintf(output, "%s      Count: %d, Minimum: %d, Maximum: %d, Total: %12.0f\n",
                prefix, count, minimum, maximum, 1.0e9*totalB + 1.0*totalA);

        // Determine the bar scaling factor
        double scale;
        if (second < (0.2*peak))
            scale = (1.0*peakBarHeight)/(1.0*second);
        else
            scale = (1.0*peakBarHeight)/(1.0*peak);

        // Bar for negative values
        if (items[size+2] > 0) {
            fprintf(output, "%s      - #s  %10d  ", prefix, items[size+2]);
            printBar(items[size+2], scale, output, prefix);
        }

        // Main bars
        for (int i=beginning; i <= end; i+=step) {
            // Accumulate bars together for "long" histograms
            int itemPrint = 0;
            for (int j=i; j < i+step; j++)
                itemPrint += items[j];

            // And print the bar
            fprintf(output, "%s      %4d  %10d  ",prefix,i,itemPrint);
            printBar(itemPrint, scale, output, prefix);
        }

        // Bar for "tail" values
        if (items[size+1] > 0) {
            fprintf(output, "%s      > #s  %10d  ",prefix,items[size+1]);
            printBar(items[size+1], scale, output, prefix);
        }
    }
    else
        fprintf(output, "%s      No values present\n", prefix);

    // And make some space
    fprintf(output,"%s\n", prefix);
}

// The add function tosses a new entry into the histogram
void Histogram::add (int newItem) {
    // Check for minimum/maximum
    if (count == 0) {
        minimum = newItem;
        maximum = newItem;
    } else {
        if (newItem < minimum) minimum = newItem;
        if (newItem > maximum) maximum = newItem;
    }

    // Increment the totals
    totalA += newItem;
    if (totalA > 1000000000) {
        totalA -= 1000000000;
        totalB += 1;
    }
    count += 1;

    // Increment the bins
    if ((newItem <= size) && (newItem >=0)) {
        items[newItem] += 1;
    }
    else if (newItem > size) {
        items[size + 1] += 1;
    }
    else { // newItem negative 
        items[size + 2] += 1;
    }
}

// The multiadd function tosses many copies of an item
//   into the histogram at once
void Histogram::multiAdd(int newItem, int inCount) {
    // Skip everything if we're not adding anything
    if (inCount > 0) {
        // Check for minimum/maximum
        if (count == 0) {
            minimum = newItem;
            maximum = newItem;
        }
        else {
            if (newItem < minimum) 
                minimum = newItem;
            if (newItem > maximum) 
                maximum = newItem;
        }

        // Increment the totals
        totalA += newItem*inCount;
        while (totalA > 1000000000) {
            totalA -= 1000000000;
            totalB += 1;
        }
        count += inCount;

        // Increment the bins
        if ((newItem <= size) && (newItem >=0)) {
            items[newItem] += inCount;
        }
        else if (newItem > size) {
            items[size + 1] += inCount;
        } else { // newItem negative
            items[size + 2] += inCount;
        }
    }
}
